
template<class T, int count>
class HeapSort {
public:
	static void sort(T* array) {

		heapify(array);
	 
	    int end = count-1;
		while (end > 0) {
	        std::swap(array[end], array[0]);
	      	--end;
	        siftDown(array, 0, end);
		}
	}
private:
	static void heapify(T* array) {
		int start = (count - 2) / 2;

		while (start >= 0) {
			siftDown(array, start, count-1);
			--start;
		}
	}
	static void siftDown(T* array, int start, int end) {

		int root = start;

		while (root * 2 + 1 <= end) {
			int child = root * 2 + 1;
			int swap = root;
			if (array[swap] < array[child]) {
				swap = child;
			}
			if (child+1 <= end && array[swap] < array[child+1]) {
			    swap = child + 1;
			}
			if (swap != root) {
			    std::swap(array[root], array[swap]);
			    root = swap;
			} else {
				return;
			}
		}
	}
};
